//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 
//输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
//
// 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
// Related Topics 数组 二分查找 分治 
// 👍 4353 👎 0

/**
 * @author DaHuangXiao
 */
package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.lang.reflect.Parameter;
import java.util.Arrays;
import java.util.Collections;

public class MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        Solution solution = new MedianOfTwoSortedArrays().new Solution();
        System.out.println(solution.findMedianSortedArrays(new int[]{1,2}, new int[]{3}));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Max = Arrays.stream(nums1).max().getAsInt();
        int nums2Max = Arrays.stream(nums2).max().getAsInt();
        int nums1Min = Arrays.stream(nums1).min().getAsInt();
        int nums2Min = Arrays.stream(nums2).min().getAsInt();

        int l = Math.min(nums1Min,nums2Min);
        int r = Math.max(nums1Max,nums2Max);

        int allLen = nums1.length+ nums2.length;

        if (allLen%2!=0) {
            while (l < r) {
                int mid = l + (r - l) / 2;
                int c = count(nums1, nums2, mid);
                if (c >= (allLen+1) / 2) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            return l;
        }else {
            while (l < r) {
                int mid = l + (r - l) / 2;
                int c = count(nums1, nums2, mid);
                if (c >= allLen / 2) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
//            System.out.println(l);
            int r1 = find(nums1,l);
            int r2 = find(nums2,l);
            int rr1 = 0;
            int rr2 = 0;
            if (r2 +1 <= nums2.length-1){
                rr2 = nums2[r2+1];
            }
            if (r1 +1 <= nums1.length-1){
                rr1 =nums1[r1+1];
            }
//            System.out.println(rr1+","+rr2);
            return (Math.max(rr1,rr2)+l)*1.0/2;

        }
    }
        private int count(int[] nums1, int[] nums2, int mid) {
            int count = 0;
            int c1 = find(nums1,mid);
            int c2 = find(nums2,mid);
            if (c1>=0 && nums1[c1]==mid){
                count++;
            }
            if (c2>=0&&nums2[c2]==mid){
                count++;
            }
            count=count+Math.max(c1,0)+Math.max(c2,0);
            return count;
        }

        private int find(int[] nums, int target) {
            int l = 0;
            int r = nums.length-1;
            while (l<r){
                int mid = l+(r-l)/2;
                if (nums[mid]>=target){
                    r = mid;
                }else{
                    l = mid+1;
                }
            }
            if (nums[l]==target){
                return l;
            }else {
                if (l==0){
                    return -1;
                }else {
                    return l;
                }
            }

        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}